NetNews Offline 2/NetNews Offline Volume 2.iso/news/comp/std/c/707

Internet Message Format | 1996-08-06 | 6KB

Path: mail2news.demon.co.uk!genesis.demon.co.uk
From: Lawrence Kirby <[e-mail]>
Newsgroups: comp.std.c
Subject: Re: Restrictions on qsort compare function?
Date: Mon, 08 Apr 96 13:56:53 GMT
Organization: none
Message-ID: <[e-mail]>
References: <4iokop$[e-mail]> <4iqjar$[e-mail]> <4jgltp$[e-mail]> <[e-mail]> <4k28t4$[e-mail]> <[e-mail]> <4k69bf$[e-mail]>
Reply-To: [e-mail]
X-NNTP-Posting-Host: genesis.demon.co.uk
X-Newsreader: Demon Internet Simple News v1.27
X-Mail2News-Path: genesis.demon.co.uk

In article <4k69bf$[e-mail]>
           [e-mail] "Peter Curran" writes:

>On Fri, 05 Apr 96 17:49:42 GMT in article <[e-mail]>
>    Lawrence Kirby <[e-mail]> (Lawrence Kirby) wrote:
>
>>If you can find any definition as to what the behaviour should be with your
>>comparison function, explain what it is. Otherwise the behaviour is
>>undefined.
>
>IMHO, qsort() is required to return an array that is sorted according to the
>criteria implied by the comparison function.  That is, at the point where qsort
>returns, the array must match the order implied by the comparison function.

But if the comparison function is inconsistent it implies no order at all.
If there is no ordering that is consistent with the values returned by the
comparison function then clearly your requirement cannot be fulfilled.

> If
>the comparison function definition is such that the order changes (although the
>*definition* of the order must remain fixed), then IMHO the current wording of
>the standard can be read as meaning that it is qsort's problem to deal with it.

No, qsort() is defined as a sorting function and what you describe is not
a valid sorting operation.

>This all hinges on how one interprets the word "considered" in the standard -

The critical word is 'sorted'. I suggest you read section 5 (i.e. the
first section of chapter 5) in Knuth Vol 3 to get a reasonable idea of what
a sort is. I repeat that it is not the job of the C standard to define
basic computer science terms. Particularly relevant:

"An ordering relation ``<'' is specified on the keys so that, for any three
 key values a, b, c, the following conditions are satisfied:

 i)  Exactly one of the possibilities a < b, a = b, b < a is true. (This is
     the law of trichotomy.)

 ii) If a < b and b < c, then a < c. (The law of transitivity.)

...

  The goal of sorting is to determine a permutation p(1)p(2)...p(N) of
the records, which puts the keys in nondescending order:

         K     <= K     <= ... <= K
          p(1)     p(2)            p(N)
"

What you suggest above is not a valid ordering relation so cannot be used
in a sort.

>that is a very vague term to use in a standard, and IMHO can reasonably lead to
>confusion.  If a "snapshot" is taken at the time qsort() returns, the array
> must
>match order implied by the comparison function.  If the definition of the
>comparison criteria cannot provide a definite sort order for the array at any
>instant, then I agree that it is invalid, but if it does provide such an
>definite order at any instant, then I think the current standard permits it.

What do you mean 'at any instant'? The relation doesn't have license to
change during the sort operation.

>Let me give another example of a problematic comparison function that seems to
>me to satisfy all the requirements of the standard, but leads, I think, to
>unintended problems for implementing qsort.
>
>The comparison function returns 1 if the first value is greater than the second
>value, or -1 if the second   However, if they are equal, the function then
>compares the values of the pointers to the parameters (the actual arguments of
>the function) - if the first is greater, 1 is returned, if the second is
> greater
>-1 is returned, otherwise 0 is returned.

>This function is a (misguided) attempt to create a stable sort.  It is only a
>valid comparison function if qsort() only passes pointers to elements in the
>array being sorted to the comparison function - otherwise, the pointer
>comparisons are (probably) undefined.

OK, however since the algorithm is unspecified you can't say any more than
this results in undefined behaviour.

  This comparions function will "work"
>(i.e. not produce undefined behaviour) for some possible implementations of
>qsort(), but not others.  It would also produce a consistent sort order for
> some
>implementations, but not others.  (I think Bubble Sort could be implemented
> with
>these restriction.  Quicksort would be trickier, or a lot slower.)

Whether a particular qsort() 'works' or not is not important, only whether
all implementations are guaranteed to work or not i.e. whether the code
is strictly conforming (apart from the issue of the unspecified order for
equal keys).

>So - is this comparison function legal or not?  I cannot see anything in the
>standard that disallows it.  I think the requirement to avoid undefined
>behaviour in this case can reasonably be interpreted as falling on qsort(), not
>on the comparison function.  I am sure the committee never intended such a
>think, but I the current standard can reasonably be read as containing them.

Assuming that the particular qsort() implementation does only pass
pointers to the array's elements you violate the rules for the relation,
certainly i) and probably ii) also. So the operation as a whole isn't a sort
and the standard defines no behaviour for it.

--
-----------------------------------------
Lawrence Kirby | [e-mail]
Wilts, England | [e-mail]
-----------------------------------------